package combine;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * =================================
 * <p>
 * Created by cjj on 18-10-12.
 * <p>
 * 描述: 用户分配给管理者问题
 */

public class AllocMoneyToUser {

    public static final int N = 3;
    public static final int M = 50;

    //用来保存每个用户分到的money
    Map<Integer, Double> map = new HashMap(N);
    Map<Integer, Double> mapResult = new HashMap(N);
    //用来管理者管理那些用户
    Map<Integer, List<Customer>> customerMap = new HashMap(M);

    {
        for (int k = 0; k < N; k++) {
            map.put(k, 0.0);
        }
    }

    /**
     * 从m个人，每个人的金额不通，必须有n个（n<=m）来分别管理，要求管理的用户金额相差最小，给出最优方案
     */
    @Test
    public void count() {

        int i;
        //用户对象，级他们充值的钱，用一个list对象表示，也可以用map表示
        List<Customer> users = new ArrayList();
        for (i = 0; i < M; i++) {
            Customer customer = new Customer();
            customer.setUsername("laochen" + i);
            customer.setMoney(Math.random() * 100);
            users.add(customer);
        }
        step(N, M, users);
        System.out.println(minCompare);
        for (int k = 0; k < N; k++) {
            Double aDouble = mapResult.get(k);
            System.out.println(aDouble);
        }
    }


    double minCompare = Integer.MAX_VALUE;

    public void step(int n, int m, List<Customer> userss) {
        int i;
        for (i = m - n + 1; i > m / n; i--) {
            //对每一个进行排列组合
            combine(i, m, n, userss);
        }


    }

    public void combine(int n, int m, int flagn, List<Customer> userss) {
        int i, j, k, p;

        int[] b = new int[m];

        for (i = 0; i < n; i++) {
            b[i] = 1;
        }
        int flag[] = new int[m];
        double tempMinMoney = 0;
        List<Customer> customers = new ArrayList();
        do {
            for (i = 0; i < m - 1; i++) {
                if (b[i] == 1 && b[i + 1] == 0) {
                    b[i] = 0;
                    b[i + 1] = 1;

                    //让最左边的数为1,不够补0
                    if (i >= n && flag[i + 1] == 0) {
                        for (j = 0; j < i; j++) {
                            if (j < n - 1) {
                                b[j] = 1;
                            } else {
                                b[j] = 0;
                            }
                        }
                        flag[i + 1] = 1;
                    }
                    customers.clear();
                    //保存此时的用户数据
                    for (j = 0; j < m; j++) {
                        if (b[j] == 1) {
                            System.out.print((j + 1) + " ");
                            map.put(flagn - 1, map.get(flagn - 1) + userss.get(j).getMoney());
                        } else {
                            customers.add(userss.get(j));
                        }
                    }
                    System.out.println();
                    if (flagn - (m - n) == 1) {
                        for (j = 0; j < flagn - 1; j++) {
                            map.put(j, map.get(j) + customers.get(j).getMoney());
                        }
                        tempMinMoney = 0;
                        for (k = 0; k < N; k++) {
                            for (p = k + 1; p < N; p++) {
                                tempMinMoney += Math.abs(map.get(k) - map.get(p));
                            }
                        }

                        if (minCompare > tempMinMoney) {
                            minCompare = tempMinMoney;
                            //保存customer
                            mapResult.clear();
                            mapResult.putAll(map);
                        }
                        for (j = 0; j < flagn; j++) {
                            map.put(j, 0.0);
                        }
                        customers.clear();
                    } else {
                        if (flagn > 2) {
                            //继续迭代step
                            step(flagn - 1, m - n, customers);
                            map.put(flagn - 1, 0.0);
                        } else {
                            //对剩余的进行计算
                            for (j = 0; j < customers.size(); j++) {
                                map.put(flagn - 2, map.get(flagn - 2) + customers.get(j).getMoney());
                            }
                            tempMinMoney = 0;
                            for (k = 0; k < N; k++) {
                                for (p = k + 1; p < N; p++) {
                                    tempMinMoney += Math.abs(map.get(k) - map.get(p));
                                }
                            }
                            if (minCompare > tempMinMoney) {
                                minCompare = tempMinMoney;
                                mapResult.clear();
                                mapResult.putAll(map);
                            }
                            //结束一次运算清空临时数据
                            for (k = 0; k < flagn; k++) {
                                map.put(k, 0.0);
                            }
                            customers.clear();

                        }
                    }
                    break;
                }
            }

        } while (isFinishCount(b, n, m));
    }

    public boolean isFinishCount(int[] b, int n, int m) {
        for (int i = m - 1; i >= m - n; i--) {
            if (b[i] != 1) {
                return true;
            }
        }
        return false;
    }


}


